|
計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである（''Symmetric Logspace'' の略）。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。SLは本来は「対称性チューリング機械」を使って定義されるが、非常に複雑な定式化であるため、 実際にはUSTCON問題への還元性の方がよく使われる。 USTCON は STCON（有向到達可能性）問題の特殊ケースである。STCONは有向グラフでの2つの頂点間の経路の有無を判定する問題であり、NL-完全である。USTCON は SL-完全なので、USTCONの解法の進歩は SL にも影響がある。 2004年10月、Omer Reigngold は SL = L であることを示した。 == 背景 == 1982年、Lewis と Papadimitriou によってSLが最初に定義された〔Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms . Manuscript. 1998.〕〔Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. ''Theoretical Computer Science''. pp.161-187. 1982.〕。彼らはUSTCONの属する複雑性クラスを探していて、当時は非決定性が必要とされないにも関わらず NL とされていた。彼らは「対称性チューリング機械」を定義してSLを定義し、USTCONがSL-完全であることを示し、次が成り立つことを証明した。 : ここで、Lは通常のチューリング機械で対数領域で解ける問題のクラスであり、NLは非決定性チューリング機械で対数領域で解ける問題のクラスである。後述するように Reingold は、対数領域に限定したとき、対称性チューリング機械と通常の決定性チューリング機械の能力が同じであるという事実を示した。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「SL (計算複雑性理論)」の詳細全文を読む スポンサード リンク
|